Data compression is widely used in the processes of transmitting and storing data, especially when transmitting data via a communication channel that is slow, expensive, and/or not reliable. Data compression is a process that reduces the number of bits of information that are used to represent information in a data file or data stream. Data compression is possible because of the existence of certain patterns or strings of information often found in a data file. In particular, certain strings of data may appear in a number of locations within the data file and it is sufficient to identify such repeated strings merely by their position within the file. By taking advantage of such redundancies in the information of a file, it is possible to represent the exact same information using fewer bits of data.
The importance of data compression arises for two primary reasons. First, when data is represented in a compressed form, it requires less bandwidth and less time to transmit this information between different devices, for example between devices in a network, or between different components of a system. Additionally, when storing data, data compression supports storing of the same data file using a smaller amount of memory. Therefore, compressed data is data that may be transmitted faster and stored more efficiently than uncompressed data.
Numerous methods are found in the art for compressing data files. However, these methods generally have shortcomings related to restrictions on the length of match strings that can be encoded and the processing overhead associated with the use of escape characters. Generally, regarding the use of escape characters, existing data compression algorithms use a special character to signal whether the characters that follow the special character are normal data or meta-data; this special character is called the escape character. When compressing files, e.g., binary files, it is not easy to define the escape character. Furthermore, the application of the escape character introduces overhead in the compressed file that impacts the efficiency of the compression.
In the drawings, the same reference numbers identify identical or substantially similar elements or acts. To easily identify the discussion of any particular element or act, the most significant digit or digits in a reference number refer to the Figure number in which that element is first introduced (e.g., element 104 is first introduced and discussed with respect to FIG. 1).